1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <cstdio>
#include <stack>
#define LL long long
const int maxn = 5e5 + 5;
using namespace std;
struct E{
int to, nxt;
}e[maxn];
int head[maxn], tot = 0;
void addedge(int u, int v){
e[++tot].to = v, e[tot].nxt = head[u];
head[u] = tot;
}
char str[maxn];
int fa[maxn], f[maxn], sum[maxn];
stack <int> s; LL ans = 0;
void dfs(int cur){
if (str[cur] == '(') s.push(cur);
int tmp = -1;
if (str[cur] == ')'){
if (!s.empty()){
f[cur] = f[fa[s.top()]] + 1;
tmp = s.top();
s.pop();
}
} sum[cur] = f[cur] + sum[fa[cur]];
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
dfs(v);
}
if (str[cur] == '(' && !s.empty()) s.pop();
else if (tmp != -1) s.push(tmp);
ans ^= (1ll * cur * sum[cur]);
}
int n;
int main(){
scanf("%d%s", &n, str + 1);
for (int i = 2; i <= n; i++){
scanf("%d", fa + i);
addedge(fa[i], i);
}
dfs(1);
printf("%lld\n", ans);
return 0;
}
|